package MyArithmetic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> listall = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0;i<nums.length;i++){

            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            while(left<right&&left<nums.length&&right>i){
                int sum = nums[left] + nums[right] + nums[i];
                if(sum>0){
                    right--;
                }else if(sum<0){
                    left++;
                }else{
                    List<Integer> list1 = new ArrayList<>();
                    list1.add(nums[left]);
                    list1.add(nums[right]);
                    list1.add(nums[i]);
                    listall.add(list1);

                    while((left<right&&nums[right] == nums[right-1])){
                        right--;
                    }
                    while((left<right&&nums[left] == nums[left+1])){
                        left++;

                    }
                    right--;
                    left++;
                }
            }

            
        }
        return listall;
    }

    public static void main(String[] args) {
        Solution s1 = new Solution();
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(s1.threeSum(nums));
    }
}